/**
 * @param {number[]} stones
 * @return {number}
 */
 var lastStoneWeightII = function(stones) {
  // 这个题目的主要思路就是将这个石头分成重量相近额两堆 那么都是在哎sum/2附近的最好
  // 所以可以使用背包问题 背包的容量就是和的一半 
  // 物品的重量和价值救赎stone[i]
  // dp[j]表示j容量的背包能装的价值是多少
  let sum = stones.reduce((p,val)=>p+val) // 求的这个的sum
  // 对sum/2去小的值 用这个值生成背包容量
  let size = Math.floor(sum/2)
  let dp = new Array(size+1).fill(0)
  // 遍历物品也就是石头
  let len = stones.length
  for(let i = 0;i < len;i++){
      // 遍历背包容量 从最大容量触发 一直到这个容量小于当前物品的重量
      for(let j = size;j >= stones[i];j--){
          dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i])
      }
  }
  // 遍历完成找出最大的dp[size] 表示sum/2的背包能装多少的石头
  // 剩下的石头就是 sum - dp[size] // 这个值肯定大于dp[size] 因为前面的去的是较小的值
  // 碰撞后的石头就是 sum -dp[size] - dp[size]
  return sum - dp[size] - dp[size]
};